#include "big_int.h"

big_int::big_int(const std::string& s)
{
   int first = 0;
   is_positive = true;
   
   if (s[0] == '-')
   {
      is_positive = false;
      first++;
   }

   int n = s.length();
   for (int i = n; i > first; i -= K)
   {
      if (i - first < K)
         digits.push_back(atoi(s.substr(first, i - first).c_str()));
      else
         digits.push_back(atoi(s.substr(i - K, K).c_str()));
   }

   delete_leading_zeros();

   fix_sign();
}

big_int::big_int(long long x)
{
   is_positive = true;
   if (x < 0)
   {
      is_positive = false;
      x = x * (-1);
   }
   
   digits.push_back(x);
}

void big_int::swap(big_int& x)
{
   std::swap(is_positive, x.is_positive);
   digits.swap(x.digits);
}

bool operator<(const big_int& a, const big_int& b)
{
   return compare(a, b, 0) < 0;
}

bool operator>(const big_int& a, const big_int& b)
{
   return compare(a, b, 0) > 0;
}

bool operator==(const big_int& a, const big_int& b)
{
   return compare(a, b, 0) == 0;
}

bool operator!=(const big_int& a, const big_int& b)
{
   return compare(a, b, 0) != 0;
}

bool operator>=(const big_int& a, const big_int& b)
{
   return compare(a, b, 0) >= 0;
}

bool operator<=(const big_int& a, const big_int& b)
{
   return compare(a, b, 0) <= 0;
}

big_int operator+(const big_int& a, const big_int& b)
{
   big_int result = a;
   result += b;
   return result;
}

big_int operator-(const big_int& a, const big_int& b)
{
   big_int result = a;
   result -= b;
   return result;
}

big_int operator*(const big_int& a, const big_int& b)
{   
   big_int result = a;
   result *= b;
   return result;
}

namespace
{
   std::pair<int, big_int> find_digit(const big_int& remainder, const big_int& divisor, int shift)
   {
      int low = 0;
      int high = big_int::BASE;
      big_int c;

      while (high - 1 > low) 
      {
         c = divisor * ((high + low) / 2);

         if (compare(remainder, c, shift) > 0)
         {
            low = (high + low) / 2;
            continue;
         }

         high = (high + low) / 2;

         if (compare(remainder, c, shift) < 0)
         {
            continue;
         }

         low = high;
      }

      c = divisor * ((high + low) / 2);

      return std::make_pair((low + high) / 2, c);
   }

  
}

 std::pair<big_int, big_int> big_int::qoutient_and_remainder_division(const big_int& a1, const big_int& b1)
   {
      big_int a = a1;
      big_int b = b1;
      assert(b != 0);

      big_int remainder = a;
      int shift = a.digits.size() - b.digits.size();

      if ((shift > -1) && (a.compare(b, shift) < 0))
         shift--;

      big_int quotient;
      quotient.digits.resize(0);

      if (shift > -1)
         quotient.digits.resize(shift + 1);
        
      while (shift >= 0)
      {
         std::pair<int, big_int> res = find_digit(remainder, b, shift);
         quotient.digits[shift] = res.first;
       
         if (remainder.compare(res.second, 0) > 0)
            subtract(remainder, res.second, shift);
         else
         {
            subtract(res.second, remainder, shift);
            remainder = res.second;
         }
                
         shift--;
      }

      if (quotient.digits.size() == 0)
         quotient.digits.push_back(0);
      return std::make_pair(quotient, remainder);
   }
big_int operator/(const big_int& a, const big_int& b)
{
   big_int result = a;
   result /= b;
   return result;
}

big_int operator%(const big_int& a, const big_int& b)
{
   big_int result = a;
   result %= b;
   return result;
}

big_int big_int::operator-()
{
   big_int result = *this;
   result.is_positive = !result.is_positive;
   result.fix_sign();
   return result;
}

big_int& big_int::operator+=(const big_int& a)
{
   if (is_positive != a.is_positive)
   {
      big_int b = *this;
      big_int a1 = a;
      bool flag = is_positive;

      *this = b.abs() - a1.abs();

      if (b.abs() > a1.abs())
         is_positive = flag;
      else
         is_positive = !(flag);
      
      fix_sign();

      return *this;
   }

   big_int b = a;
   int n = std::max(digits.size(), b.digits.size());
   long long tr = 0;
   big_int result;
   result.digits.resize(0);

   for (int i = 0; i < n; i++)
   {
      result.digits.push_back((digits.at(i) + b.digits.at(i) + tr) % big_int::BASE);
      tr = (digits.at(i) + b.digits.at(i) + tr) / big_int::BASE;
   }
   if (tr != 0)
      result.digits.push_back(tr);
   
   result.delete_leading_zeros();

   result.is_positive = is_positive;
   
   result.fix_sign();

   *this = result;
   return *this;
}

big_int& big_int::operator-=(const big_int& a)
{
   if (is_positive != a.is_positive)
   {
      big_int b1 = *this;
      big_int b = *this;
      big_int a1 = a;
      *this = a1.abs() + b1.abs();
      is_positive = b.is_positive;
      
      fix_sign();
      return *this;
   }

   big_int b = *this;
   big_int a1 = a;
   if (b.abs() < a1.abs())
   {
      big_int b = *this;
      *this = -(a - b);
      return *this;
   }

   b = a;
   int n = std::max(digits.size(), b.digits.size());
   long long tr = 0;
   big_int result;
   result.digits.resize(0);

   for (int i = 0; i < n; i++)
   {
      if (digits.at(i) - tr < b.digits.at(i))
      {
         result.digits.push_back(big_int::BASE + digits.at(i) - tr - b.digits.at(i));
         tr = 1;
      } else
      {
         result.digits.push_back(digits.at(i) - tr - b.digits.at(i));
         tr = 0;
      }
   }

   result.delete_leading_zeros();

   result.is_positive = is_positive;

   result.fix_sign();

   *this = result;
   return *this;
}

big_int& big_int::operator*=(const big_int& a)
{
   big_int result;
   big_int b = a;

   int n = b.digits.size();
   int m = digits.size();

   big_int x;
   for (int i = 0; i < n; i++)
   {
      x = 0;
      x.digits.resize(i);

      long long tr = 0;
      for (int j = 0; j < m; j++)
      {
         x.digits.push_back((digits.at(j) * b.digits.at(i) + tr) % big_int::BASE);
         tr = (digits.at(j) * b.digits.at(i) + tr) / big_int::BASE;
      }
      if (tr != 0)
         x.digits.push_back(tr);

      result += x;
   }

   result.delete_leading_zeros();

   if (is_positive != b.is_positive)
      result.is_positive = false;

   result.fix_sign();

   *this = result;

   return *this;
}

big_int& big_int::operator/=(const big_int& b)
{
   big_int a = *this;
   big_int b1 = b;
   std::pair<big_int, big_int> res = qoutient_and_remainder_division(a.abs(), b1.abs());
   big_int result = res.first;
   
   if (is_positive == b.is_positive)
      result.is_positive = true;
   else
      result.is_positive = false;
   
   result.fix_sign();

   *this = result;

   return *this;
}

big_int& big_int:: operator%=(const big_int& b)
{
   big_int a = *this;
   big_int b1 = b;
   std::pair<big_int, big_int> res = qoutient_and_remainder_division(a.abs(), b1.abs());
   big_int result = res.second;
   
   result.is_positive = is_positive;
   
   result.fix_sign();

   *this = result;
   return *this;
}

int big_int::compare(const big_int& b, int shift)
{
   if (is_positive != b.is_positive)
      return is_positive - b.is_positive;
   
   int k = 1;
   if (!is_positive)
      k = -1;

   if (digits.size() !=  b.digits.size() + shift)
   {
      return k * (digits.size() - b.digits.size() - shift);
   }

   int i = digits.size() - 1;

   while ((i >= shift) && (digits.at(i) == b.digits.at(i - shift)))
   {
      i--;
   }

   if (i >= shift)
   {
      return k * static_cast<int>(digits.at(i) - b.digits.at(i - shift));
   }

   for (int i = 0; i < shift; i++)
   {
      if (digits.at(i) > 0) 
         return k * 1;
   }

   return 0;
}

int compare(big_int a, const big_int& b, int shift)
{
   return a.compare(b, shift);
}

void big_int::subtract(big_int& a, const big_int& b1, int shift)
{
   big_int b = b1;
   int n = b.digits.size();
   
   for (int i = 0; i < n; i++)
   {
      a.digits[i + shift] -= b.digits.at(i);
      int j = i;
      
      int nn = a.digits.size();
      while ((a.digits[j + shift] < 0) && (j < nn))
      {
         a.digits[j + shift] += big_int::BASE;
         a.digits[j + shift + 1]--;
         j++;
      }

      a.delete_leading_zeros();
   }
}

std::istream& operator>>(std::istream& in, big_int& a)
{
   while (isspace(in.peek()))
      in.get();

   if (in.eof())
   {
      in.setstate(std::ios::failbit);
      return in;
   }

   std::string s;
   if (in.peek() == '-' || in.peek() == '+')
   {
      if (in.peek() == '-')
         s.push_back('-');
      in.get();
   }
   
   if (!isdigit(in.peek()))
   {
      in.setstate(std::ios::failbit);
      return in;
   }

   while (isdigit(in.peek()))
   {
      s.push_back(static_cast<char>(in.get()));
   }

   a = 0;
   a.digits.resize(0);
   a = big_int(s);

   return in;
}

std::ostream& operator<<(std::ostream& out, const big_int& a)
{
   int n = a.digits.size();
   if (n == 0)
      return out;

   if (!a.is_positive)
      out << '-';

   out << a.digits.at(n - 1);

   for (int i = n - 2; i >= 0; --i)
   {
      int len = 1;
      long long x = a.digits.at(i);
      while (x > big_int::EXTERNAL_BASE - 1)
      {
         len++;
         x = x / big_int::EXTERNAL_BASE;
      }

      for (int j = len; j < big_int::K; j++)
         out << "0";

      out << a.digits.at(i);
   }

   return out;
}

big_int big_int::abs()
{
   is_positive = true;
   return *this;
}

big_int abs(const big_int& x)
{
   big_int result = x;
   result.abs();
   return result;
}

void big_int::delete_leading_zeros()
{
   while (digits.size() > 1 && digits.back() == 0)
      digits.pop_back();
}

void big_int::fix_sign()
{
   if (digits.size() == 1 && digits[0] == 0)
      is_positive = true;
}

